package ACWing.mathematicalknowledge.欧几里得;
//878. 线性同余方程

import java.util.Scanner;

/**
 * @author :chenjie
 * @date :Created 2023/1/12 20:57
 */
public class LinearCongruenceEquation {
    static int x,y;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        while (n-->0){
            int a=sc.nextInt();
            int b=sc.nextInt();
            int m=sc.nextInt();
            int gcd = gcd(a, m);
            if(b%gcd==0){
                System.out.println((long) x*(b/gcd)%m);
            }else {
                System.out.println("impossible");
            }
        }
    }
    public static int gcd(int a,int b){
        if(b==0){
            x=1;y=0;

            return a;
        }
        int d= gcd(b,a%b);

        int tmp = x;
        x = y;
        y = tmp - a / b * y;
        return d;
    }
}
